package com.tgy.programmer_code_interview_guide._08_array_matrix;

import java.util.HashMap;
import java.util.Map;

/**
 * @Author: tgy
 * @Date: 2/1/21 3:46 PM
 */
public class _11_未排序数组中累加和为指定值的最长子数组 {

    public static int findSubMaxLen(int[] nums, int k) {


        Map<Integer,Integer> map = new HashMap<>();
        map.put(0,-1);
        int maxLen = 0;
        int sum = 0;
        for (int i = 0; i < nums.length; i++) {

            sum += nums[i];
            int distance = sum - k;

            if (map.keySet().contains(distance)) {

               maxLen = Math.max(maxLen,i -  map.get(distance));
            }

            if (!map.keySet().contains(sum)) {

                map.put(sum,i);
            }
        }

        return maxLen;
    }

    public static void main(String[] args) {

        int len = findSubMaxLen(new int[]{-2,2,1,1,1},3);
        System.out.println(len);
    }
}
